/*
 * @Author: chyang0822 270917365@qq.com
 * @Date: 2024-10-25 17:30:28
 * @LastEditors: chyang0822 270917365@qq.com
 * @LastEditTime: 2024-10-28 13:16:09
 * @FilePath: /Project-DMAI-Deploy/tutorials/concurrency/listing_4.13.cpp
 * @Description: 
 * 
 * Copyright (c) 2024 by ${git_name_email}, All Rights Reserved. 
 */
#include <list>
#include <algorithm>
#include <future>
template<typename T>
std::list<T> parallel_quick_sort(std::list<T> input)
{
    if(input.empty())
    {
        return input;
    }
    std::list<T> result;
    result.splice(result.begin(),input,input.begin());
    T const& pivot=*result.begin();
    auto divide_point=std::partition(input.begin(),input.end(),
        [&](T const& t){return t<pivot;});
    std::list<T> lower_part;
    lower_part.splice(lower_part.end(),input,input.begin(),
        divide_point);
    std::future<std::list<T> > new_lower(
        std::async(&parallel_quick_sort<T>,std::move(lower_part)));
    auto new_higher(
        parallel_quick_sort(std::move(input)));
    result.splice(result.end(),new_higher);
    result.splice(result.begin(),new_lower.get());
    return result;
}

int main()
{
    std::list<int> input;
    input.push_back(10);
    input.push_back(12);
    input.push_back(7);
    input.push_back(15);
    input.push_back(5);
    std::list<int> output = parallel_quick_sort(input);
    return 0;
}
